1814E - Chain Chips - CodeForces Solution

#pragma GCC optimize("O3")
#ifdef ONLINE_JUDGE
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#pragma GCC optimize("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#include <bits/stdc++.h>
#include <deque>
#include <type_traits>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
template<typename KeyType=int,typename Mapped=__gnu_pbds::null_type,typename Cmp_Fn=std::less<KeyType>,typename Tag=__gnu_pbds::rb_tree_tag,template<typename Const_Node_Iterator,typename Node_Iterator,typename Cmp_Fn_,typename Allocator_>class Node_Update=__gnu_pbds::tree_order_statistics_node_update,typename Allocator=std::allocator<char>>using ordered_set_t=__gnu_pbds::tree<KeyType,Mapped,Cmp_Fn,Tag,Node_Update,Allocator>;const int GRANDOM=std::chrono::high_resolution_clock::now().time_since_epoch().count();struct ghash{int operator()(int x){return std::hash<int>{}(x^GRANDOM);}};template<typename KeyType>using hash_table_t=__gnu_pbds::gp_hash_table<KeyType,int,ghash>;
#define prec setprecision
namespace vh{typedef long long ll;typedef unsigned long long llu;template<typename T>constexpr T gcd(T m,T n){while(n){T t=m%n;m=n;n=t;};return m;}template<typename T>constexpr T exgcd(T a,T b,T&sa,T&ta){T q,r,sb=0,tb=1,sc,tc;sa=1,ta=0;if(b)do q=a/b,r=a-q*b,a=b,b=r,sc=sa-q*sb,sa=sb,sb=sc,tc=ta-q*tb,ta=tb,tb=tc;while(b);return a;}template<typename T>constexpr T mul_inv(T a,T b){T t1=a,t2=b,t3;T v1=1,v2=0,v3;T x;while(t2!=1)x=t1/t2,t3=t1-x*t2,v3=v1-x*v2,t1=t2,t2=t3,v1=v2,v2=v3;return(v2+b)%b;}template<typename T>constexpr T powmod(T a,T b,T MOD){if(b<0)return 0;T rv=1;while(b)(b%2)&&(rv=(rv*a)%MOD),a=a*a%MOD,b/=2;return rv;}template<typename T>constexpr inline T isqrt(T k){T r=sqrt((double)k)+1;while(r*r>k)r--;while((r+1)*(r+1)<=k)r++;return r;}template<typename T>constexpr inline T icbrt(T k){T r=cbrt((double)k)+1;while(r*r*r>k)r--;return r;}template<typename T>bool mul_overflow(T&r,T a,T b){return __builtin_mul_overflow(a,b,&r);}template<typename T1,typename T2>T1 E0(const T2&x){return get<0>(x);};template<typename T1,typename T2>T1 E1(const T2&x){return get<1>(x);};template<typename T1,typename T2>T1 E2(const T2&x){return get<2>(x);};template<typename T1,typename T2>T1 E3(const T2&x){return get<3>(x);};template<typename T1,typename T2>T1 E4(const T2&x){return get<4>(x);};template<typename T1,typename T2>T1 E5(const T2&x){return get<5>(x);};template<ll n>struct BitSize{enum{Size=BitSize<n/2>::Size+1};};template<>struct BitSize<0>{enum{Size=1};};template<>struct BitSize<1>{enum{Size=1};};
#define BITSIZE(n) (BitSize<n>::Size)
#define TREESIZE(n) ((1<<(BitSize<n>::Size + 1))+7)
#define BITMAX(n) (BitSize<n>::Size - 1)
#define DEBUG defined(VHLOCAL)
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define RALL(x) (x).rbegin(),(x).rend()
int MSB(unsigned int x){return 8*sizeof(int)-1-__builtin_clz(x|1);}int MSB(unsigned long x){return 8*sizeof(long)-1-__builtin_clzl(x|1);}int MSB(unsigned long long x){return 8*sizeof(long long)-1-__builtin_clzll(x|1);}
#define FORSUBSET(i,s) for(int i=s;i;i=(i-1)&(s))
#define FORSUBSET2(i,s) for(int i=s&(s-1);i;i=(i-1)&(s))
constexpr bool IS_PRIME(ll n){for(int i=2;i*i<=n;i++)if(n%i==0)return false;return true;}template<typename T,int min_neg>class vector_neg_index:public vector<T>{public:using vector<T>::vector;vector_neg_index(int n):vector<T>(n-min_neg){}void resize(int n){vector<T>::resize(n-min_neg);}T&operator[](int i){return vector<T>::operator[](i-min_neg);}const T&operator[](int i)const{return vector<T>::operator[](i-min_neg);}};}namespace vh{template<class T>struct like_array:is_array<T>{};template<class T,size_t N>struct like_array<array<T,N>>:true_type{};template<class T>struct like_array<vector<T>>:true_type{};template<class T>bool is_like_array(const T&a){return like_array<T>::value;}template<class T>void _R(T&x){std::cin>>x;}inline void _R(int&x){scanf("%d",&x);}inline void _R(int64_t&x){scanf("%" SCNd64,&x);}inline void _R(double&x){scanf("%lf",&x);}inline void _R(char&x){scanf(" %c",&x);}inline void _R(char*x){scanf("%s",x);}template<typename T>inline void _R(vector<T>&v,size_t ie){for(int i=0;i<ie;i++)_R(v[i]);}template<typename T>inline void _R(vector<T>&v){_R(v,v.size());}inline void R(){}template<class T,class... U>inline void R(T&head,U&... tail){_R(head);R(tail...);}template<class T>void _W(const T&x){cout<<x;}template<typename T>inline void _W(vector<T>&v,size_t ie){for(int i=0;i<ie;i++){if(i>0)_W(' ');_W(v[i]);}_W('\n');}template<typename T>inline void _W(vector<T>&v){_W(v,v.size());}template<class T>inline void _W(const vector<T>&x){for(auto i=x.begin();i!=x.end();_W(*i++))if(i!=x.cbegin())putchar(' ');}inline void W(){}template<class T,class... U>inline void W(const T&head,const U&... tail){_W(head);if(sizeof...(tail))putchar(' '),W(tail...);}template<class T,class... U>inline void WL(const T&head,const U&... tail){_W(head);putchar(sizeof...(tail)? ' ':'\n');W(tail...);}template<class T>void _RE(T&x){cin>>x;}template<class Arg,class... Args>void _RE(Arg&first,Args&... rest);void _RE(double&x){string t;_RE(t);x=stod(t);}void _RE(long double&x){string t;_RE(t);x=stold(t);}template<class T>void _RE(complex<T>&x);template<class T1,class T2>void _RE(pair<T1,T2>&p);template<class T>void _RE(vector<T>&a);template<class T,size_t SZ>void _RE(array<T,SZ>&a);template<class Arg,class... Args>void _RE(Arg&first,Args&... rest){_RE(first);_RE(rest...);}template<class T>void _RE(complex<T>&x){T a,b;_RE(a,b);x=cd(a,b);}template<class T1,class T2>void _RE(pair<T1,T2>&p){_RE(p.f,p.s);}template<class T>void _RE(vector<T>&a){for(int i=0,ie=sz(a);i<ie;i++)_RE(a[i]);}template<class T,size_t SZ>void _RE(array<T,SZ>&a){for(int i=0;i<SZ;i++)_RE(a[i]);}template<typename T>struct is_container:false_type{};template<typename T>struct is_container<vector<T>>:true_type{};template<typename T>struct is_container<set<T>>:true_type{};template<typename T,typename T2>struct is_container<map<T,T2>>:true_type{};template<typename T>struct is_container<deque<T>>:true_type{};template<typename T>struct is_container<queue<T>>:true_type{};template<class V,typename=std::enable_if_t<is_container<V>::value>>std::ostream&operator<<(std::ostream&o,const V&v){o<<"[";bool first=true;for(auto x:v){if(!first)o<<",";first=false;o<<x;}o<<"]";return o;}template<class V,typename=std::enable_if_t<is_container<V>::value>>std::istream&operator>>(std::istream&s,V&v){for(auto&x:v){s>>x;}return s;}template<typename A,typename B>std::istream&operator>>(std::istream&s,pair<A,B>&v){return s>>v.first>>v.second;}template<typename A,typename B,typename C>std::istream&operator>>(std::istream&s,tuple<A,B,C>&v){return s>>get<0>(v)>>get<1>(v)>>get<2>(v);}template<typename A,typename B,typename C,typename D>std::istream&operator>>(std::istream&s,tuple<A,B,C,D>&v){return s>>get<0>(v)>>get<1>(v)>>get<2>(v)>>get<3>(v);}template<typename A,typename B>std::ostream&operator<<(std::ostream&o,pair<A,B>x){return o<<"("<<x.first<<";"<<x.second<<")";}template<typename A,typename B,typename C>std::ostream&operator<<(std::ostream&o,tuple<A,B,C>x){return o<<"("<<get<0>(x)<<","<<get<1>(x)<<","<<get<2>(x)<<")";}template<typename A,typename B,typename C,typename D>std::ostream&operator<<(std::ostream&o,tuple<A,B,C,D>x){return o<<"("<<get<0>(x)<<","<<get<1>(x)<<","<<get<2>(x)<<","<<get<3>(x)<<")";}template<typename TH>void _dbg(const char*sdbg,TH h){cerr<<sdbg<<"="<<h<<"\n";}template<typename TH,typename... TA>void _dbg(const char*sdbg,TH h,TA... t){while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<",";_dbg(sdbg+1,t...);}
#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define debugv(x) {{cerr <<#x <<" = "; for(auto itt: x) cerr <<*itt <<", "; cerr <<"\n"; }}
#else
#define debug(...) (__VA_ARGS__)
#define debugv(x)
#define cerr if(0)cout
#endif
};namespace vh{template<typename T>int min_rotation(vector<T>s){int a=0,N=s.size();for(int b=0;b<N;b++)for(int i=0;i<N;i++){if(a+i==b||s[(a+i)%N]<s[(b+i)%N]){b+=max(0,i-1);break;}if(s[(a+i)%N]>s[(b+i)%N]){a=b;break;}}return a;};template<typename T>class StackGuard{private:T x;public:StackGuard(T x):x(x){}~StackGuard(){x();}};template<class T,class U>T fstTrue(T lo,T hi,U f){hi++;assert(lo<=hi);while(lo<hi){T mid=half(lo+hi);f(mid)? hi=mid:lo=mid+1;}return lo;}template<class T,class U>T lstTrue(T lo,T hi,U f){lo--;assert(lo<=hi);while(lo<hi){T mid=half(lo+hi+1);f(mid)? lo=mid:hi=mid-1;}return lo;}}
#define xx first
#define yy second
namespace vh{const ll inf=(ll)1e18;class Tree{public:Tree(int n){v.resize(1<<21);for(int i=0;i<(1<<20);i++)v[i][4]=0;for(int i=1<<20;i<(1<<21);i++)v[i]={inf,inf,inf,inf,2ll};for(int i=(1<<20)+n;i<(1<<21);i++)v[i]={inf,inf,inf,inf,2ll};for(int i=0;i<n;i++)upd(i,inf);}array<ll,5>calc(array<ll,5>a,array<ll,5>b){if(b[4]==2)return a;assert(a[4]!=2);array<ll,5>ans;ans[4]=0;if(a[4]){if(b[4]){ans[0]=inf;ans[1]=a[3];ans[2]=b[3];ans[3]=a[3]+b[3];}else{ans[0]=b[1];ans[1]=a[3]+min(b[0],b[1]);ans[2]=b[3];ans[3]=a[3]+min(b[2],b[3]);}}else{if(b[4]){ans[0]=a[2];ans[1]=a[3];ans[2]=min(a[2],a[0])+b[3];ans[3]=min(a[3],a[1])+b[3];}else{ans[0]=min(a[2]+min(b[1],b[0]),min(a[2],a[0])+b[1]);ans[1]=min(min(a[1],a[3])+b[1],a[3]+min(b[1],b[0]));ans[2]=min(min(a[2],a[0])+b[3],a[2]+min(b[3],b[2]));ans[3]=min(min(a[1],a[3])+b[3],a[3]+min(b[2],b[3]));}}ans[0]=min(ans[0],inf);ans[1]=min(ans[1],inf);ans[2]=min(ans[2],inf);ans[3]=min(ans[3],inf);return ans;}void upd(int x,ll y){int _n=1<<20;v[_n+x][0]=inf;v[_n+x][1]=inf;v[_n+x][2]=inf;v[_n+x][3]=y;v[_n+x][4]=1;for(int i=(_n+x)>>1;i;i>>=1){v[i]=calc(v[i<<1],v[i<<1|1]);}}ll query(){return v[1][0];}private:vector<array<ll,5>>v;};};
namespace vh{
  int main(){
    srand(GRANDOM);
    int n;cin>>n;
    vector<int>a(n+1);
    Tree tree(n+1);
    for(int i=1;i<=n-1;i++)cin>>a[i],tree.upd(i,a[i]);
    tree.upd(0,a[1]);
    tree.upd(n,a[n-1]);
    int q;cin>>q;while(q--){
      int k,x;cin>>k>>x;
      tree.upd(k,x);
      if(k==1)tree.upd(0,x);
      if(k==n-1)tree.upd(n,x);
      ll ans=(tree.query()*2);
      cout<<ans<<'\n';
    }
    return 0;
  }
};
int main(int argc,char*argv[]){
  std::cin.sync_with_stdio(false);std::cin.tie(nullptr);
  return vh::main();
}